package org.lep.leetcode.datastructure.divideandconquer.pow;

/**
 * Source : https://oj.leetcode.com/problems/powx-n/
 *
 * Created by lverpeng on 2017/7/18.
 *
 * Implement pow(x, n).
 *
 */
public class Pow {

    /**
     * 实现x^n
     * 考虑n为负数
     * 当n为偶数的时候，计算x*x，以期让n扩收缩
     *
     * @param x
     * @param n
     * @return
     */
    public double pow (int x, int n) {
        boolean sign = true;        // true：正数
        if (n < 0) {
            n = -n;
            sign = false;
        }
        double result = 1.0;
        while (n > 0) {
            if ((n & 1) == 1) {
                result *= x;
            }
            n = n >> 1;
            x *= x;
        }

        return sign ? result : 1.0 / result;
    }

    /**
     * 快速幂乘
     * 分治：划分为两个子问题x的n/2和n/2，然后分别求解
     *
     * @param x
     * @param n
     * @return
     */
    public double pow1 (double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1 || x == 0) {
            return x;
        }
        boolean signed = false;
        if (n < 0) {
            signed = true;
            n = -n;
        }
        double temp = pow1(x, n/2);
        double result = temp * temp * pow1(x, n % 2);
        if (result == 0) {
            return 0.0;
        }
        return signed ? 1.0 / result : result;
    }

    public double pow2 (double x, int n) {
        boolean signed = false;
        long ln = n;
        if (n < 0) {
            signed = true;
            ln = -ln;
        }
        double result = 1;
        while (ln > 0) {
            if (ln % 2 == 1) {
                result *= x;
            }
            x *= x;
            ln /= 2;
        }
        if (result == 0) {
            return 0;
        }
        return signed ? 1.0 / result : result;
    }

    public static void main(String[] args) {
        Pow pow = new Pow();
        System.out.println(pow.pow(0, 1) + "-" + 0);
        System.out.println(pow.pow(0, 0) + "-" + 1);
        System.out.println(pow.pow(2, 0) + "-" + 1);
        System.out.println(pow.pow(2, 3) + "-" + 8);
        System.out.println(pow.pow(2, 10) + "-" + 1024);
        System.out.println(pow.pow(2, -3) + "-" + 0.125);

        System.out.println();
        System.out.println(pow.pow1(0, 1) + "-" + 0);
        System.out.println(pow.pow1(2, 0) + "-" + 1);
        System.out.println(pow.pow1(2, 0) + "-" + 1);
        System.out.println(pow.pow1(2, 3) + "-" + 8);
        System.out.println(pow.pow1(2, 10) + "-" + 1024);
        System.out.println(pow.pow1(2, -3) + "-" + 0.125);
        System.out.println(pow.pow1(1.5, 2) + "-" + 2.25);
        System.out.println(pow.pow1(2.00000, -2147483648) + "-" + 0);

        System.out.println();
        System.out.println(pow.pow2(0, 1) + "-" + 0);
        System.out.println(pow.pow2(2, 0) + "-" + 1);
        System.out.println(pow.pow2(2, 0) + "-" + 1);
        System.out.println(pow.pow2(2, 3) + "-" + 8);
        System.out.println(pow.pow2(2, 10) + "-" + 1024);
        System.out.println(pow.pow2(2, -3) + "-" + 0.125);
        System.out.println(pow.pow2(1.5, 2) + "-" + 2.25);
        System.out.println(pow.pow2(2.00000, -2147483648) + "-" + 0);
    }
}
